package bTree.LeetCode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class 两数相加2 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }


        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int jinWei = 0;
            Stack<ListNode> stack1 = new Stack<>();
            Stack<ListNode> stack2 = new Stack<>();
            ListNode p1 = l1;
            ListNode p2 = l2;
            while (p1 != null) {
                stack1.add(p1);
                p1 = p1.next;
            }
            while (p2 != null) {
                stack2.add(p2);
                p2 = p2.next;
            }
            Deque<Integer> deque = new ArrayDeque<>();
            while (!stack1.isEmpty() && !stack2.isEmpty()) {
                int val1 = stack1.pop().val;
                int val2 = stack2.pop().val;
                int i = val1 + val2+jinWei;
                int i1 = i % 10;
                int i2 = i / 10;
                deque.addFirst(i1 );
                jinWei = i2;
            }
            while (!stack1.isEmpty()) {
                int i = stack1.pop().val+jinWei;
                int i1 = i % 10;
                int i2 = i / 10;
                deque.addFirst(i1);
                jinWei = i2;
            }
            while (!stack2.isEmpty()) {
                int i = stack2.pop().val+jinWei;
                int i1 = i % 10;
                int i2 = i / 10;
                deque.addFirst(i1);
                jinWei = i2;
            }
            if (jinWei!=0) {
                deque.addFirst(jinWei);
            }
            ListNode head=new ListNode();
            head.val=deque.getFirst();
            deque.removeFirst();
            ListNode p=head;
            while (!deque.isEmpty()){
                p.next=new ListNode(deque.getFirst());
                deque.removeFirst();
                p=p.next;
            }
            return head;
        }
    }
}